Function Categories

Polynomials

p(x)p(x) is a polynomial of degree nn, n=0,1,2,n=0,1,2,\cdots is a function of the form

p(x)=anxn+an1xn1++a1x+a0p(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots +a_1x + a_0

dom(p)=Rdom(p) = \Bbb{R}
aia_i = coefficients an0a_n\ne 0 = lead coefficient a0a_0 = constant term

If aiZa_i\in\Bbb{Z}, we say p(x)p(x) has integer coefficients and we write
Z[x]=\Set of all polynomial with integer coefficient \Bbb{Z}[x]=\Set{\text{ of all polynomial with integer coefficient }}

Similarly we define Q[x],R[x],C[x]\Bbb{Q}[x], \Bbb{R}[x], \Bbb{C}[x] as the sets of all polynomials with rational, real, or complex coefficients respectively

If an=1a_n=1, we call p(x)p(x) a monic polynomial

The Fundamental Theorem of Algebra

bdg-infoThe Fundamental Theorem of Algebra
A polynomial of degree n has exactly n complex zeroes, counting multiplicity

x0x_0 is a zero of p(x)p(x) iff p(x0)=0p(x_0)=0 ie: a solution of the equation p(x)=0p(x)=0


The multiplicity of x0x_0 is the largest value of kk such that p(x)=(xx0)kq(x)p(x)=(x-x_0)^kq(x) where q(x0)0q(x_0)\ne 0

(xx0)k(x-x_0)^k is called a linear factor of p(x)p(x) of degree kk

bdg-secondaryFact If p(x)R[x]p(x)\in\Bbb{R}[x], pp has real numbers as coefficients, then p(x)p(x) can be factored into a product of linear terms (possibly repeated) if irreducible quadratic terms (possibly repeated)

Quadratic Formula

An irreducible quadratic has the form ax2+bx+c=0ax^2+bx+c=0 when b24ac<0b^2-4ac<0

bdg-infoQuadratic Formula if ax2+bx+c=0ax^2+bx+c=0 iff

x=b±b24ac2ax = \frac{-b\pm\sqrt{b^2-4ac}}{2a}

bdg-secondaryRecall r(x)=p(x)/q(x)r(x)=p(x)/q(x) where pp, qq are polynomials is called a rational function dom(r)=\SetxRq(x)0dom(r)=\Set{x\in\Bbb{R}\mid q(x)\ne 0}

Rational Functions

Basic Rational Functions

The simplest rational function is f(x)=1xf(x) = \frac{1}{x}, dom(1x)=\SetxRx0dom(\frac{1}{x})=\Set{x\in\Bbb{R}\mid x\ne 0}

Features of Graph

  1. Has vertical and horizontal asymptote
Horizontal Asymptotes

This a reflection of the fact that:

limx0±1x=±\lim_{x\to 0^\pm}\frac{1}{x}=\pm\infty

That is, the closer to x=0x=0 , f(x)=1xf(x)=\frac{1}{x} it becomes larger and larger that is f becomes unbounded

Vertical Asymptotes

This a reflection of the fact that:

limx±1x=±\lim_{x\to\infty^\pm}\frac{1}{x}=\pm\infty

That is, the higher the absolute value of xx is, the closer 1x\frac{1}{x} is to 0

General Rational Functions

r(x)=p(x)g(x)r(x)=\frac{p(x)}{g(x)}

3 types of asymptotes

  1. Vertical Asymptotes - occur at x=ax=a when g(a)=0g(a)=0
  2. Horizontal Asymptotes - occur when limx±\lim_{x\to\pm\infty} is a finite number. This means, in particular deg(p)deg(g)deg(p)\le deg(g) and if limx±\lim_{x\to\pm\infty}, the horizontal asymptote us given by y=ay=a
  3. Skew or Slant Asymptotes - occurs when deg(p)=deg(g)+1deg(p)=deg(g) + 1

Inverse Rational Functions

Certain types of rational functions, called linear fractional transformations, have inverse functions

These L.F.T's are those rational functions of the form:

f(x)=ax+bcx+d   where a,b,c,d are real constantsf(x)=\frac{ax+b}{cx+d}\ \ \text{ where a,b,c,d are real constants}

We can show that these functions are 1-1 on dom(f)=\SetxRxdc (c0)dom(f)=\Set{x\in\Bbb{R}\mid x\ne\frac{-d}{c}}\ (c\ne 0)

and we find thier inverse function f1(x)f^{-1}(x) in order to find range(f)range(f) since:

dom(f^{-1})&=\ range(f)\\ dom(f)&=\ range(f^{-1})\\

Algebraic Functions

We all have seen the concept of taking the square root of a positive number

Formally, the square root is a fractional power
We write x\sqrt{x} to mean x12x^{\frac{1}{2}}

nth Root Function

Let xRx\in\Bbb{R} We define, for n=2,3,n=2,3,\cdots
y=x1ny=x^{\frac{1}{n}} iff x=ynx=y^n

Then y=x1ny=x^{\frac{1}{n}} is called the nth root function, n=2,3,n=2,3,\cdots

The first thing we must do is determine for what values of xRx\in\Bbb{R} this formulation makes sense, ie what is dom(x1n)dom(x^{\frac{1}{n}})

When nn is even, n=2kn=2k, then y=x1n=x12ky=x^{\frac{1}{n}}=x^{\frac{1}{2k}} iff
x=y2k=(yk)20, yRx=y^{2k}=(y^k)^2\ge 0,\ \forall y\in\Bbb{R}

Thus f(x)=x1nf(x)=x^{\frac{1}{n}} is defined only for x0x\ge 0 when n is even
we don't have this restriction when nn is odd

thus,

dom(x1n)={[0,+) if n even, n>0R if n odd, n > 0 dom(x^{\frac{1}{n}})= \begin{cases} &[0,+\infty)\text{ if n even, n>0}\\ &\Bbb{R}\text{ if $n$ odd, $n$ > 0} \end{cases}

This situation is explained easily using the graphs of the functions g(x)=xng(x)=x^n and notice that f(x)=x1nf(x)=x^{\frac{1}{n}} is the inverse function of g(x)g(x)

The graph of y=xny=x^n for the two difference cases nn even and nn odd makes a difference in the graph shape, for even.

With the graph just by applying horizontal line test we know right away that the function is 1-1

We see that xnx^n, nn odd is invertible xR\forall x\in\Bbb{R}
xnx^n, n even invertible on [0,+)[0,+\infty), or (,0](-\infty,0]

Thus we also have

When nn is even (xn)1n=x, xR(x^n)^\frac{1}{n} = |x|,\ \forall x\in\Bbb{R} Why is this? Think when x2=x\sqrt{x^2} = |x|
(x1n)n=x, xR n odd(x^\frac{1}{n})^n = x,\ \forall x\in\Bbb{R}\ n\ odd
x[0,+),n even\forall x\in[0,+\infty),n\ even

The general rule is stated that you can't take even fractional roots of negative numbers in practice we restrict the domain

Other Rational Powers of x

Let r=pq>0r=\frac{p}{q}>0 where pp, qq are integers, no common divisors, q0q\ne 0

We define y=xr=(xp)1qy=x^r=(x^p)^{\frac{1}{q}} or y=xpqy=x^{\frac{p}{q}} iff yq=xpy^q=x^p

In general, to avoid problems, we will require that x0x\ge 0, to take natural powers, r>0r>0 ie dom(xr)=[0,+)dom(x^r)=[0,+\infty)

When r<0r<0, we write rt,t>0r-t, t>0 and define xr=xt=1xtx^r=x^{-t}=\frac{1}{x^t}

Now,

dom(xr)={[0,+),r>0[0,+),r<0 dom(x^r)= \begin{cases} &[0,+\infty),r>0\\ &[0,+\infty),r<0\\ \end{cases}

rr rational, rZr\notin\Bbb{Z}, with the exception noted before that

dom(x1n)={R, n positive odd integerR\\Set0,n negative odd integer dom(x^{\frac{1}{n}})= \begin{cases} &\Bbb{R},\text{ $n$ positive odd integer} &\Bbb{R}\backslash\Set{0},\text{n negative odd integer} \end{cases}

Functions like x1n,xrx^{\frac{1}{n}},x^r are special cases of a type of function called algebraic

An algebraic function is one that only has rational combinations of rational powers of polynomials

bdg-secondaryExample Of a Algebraic Function

f(x)=x+1x+x32f(x)=\sqrt{\frac{x+1}{x+x^{\frac{3}{2}}}}

bdg-infoFormal definition

y(x)y(x) is an albraic function iff \exists polynomials p0(x),,pt(x)p_0(x),\cdots ,p_t(x) such that y(x)y(x) satisfies the equation tZ+t\in\Bbb{Z}^+

pt(x)yt+pt1(x)yt1++p1(x)y+p0(x)=0 p_t(x)y^t+p_{t-1}(x)y^{t-1}+\cdots +p_1(x)y+p_0(x) = 0

bdg-secondaryExample Of a Algebraic Function
Just like previous example

[f(x)]^2&=\frac{x+1}{x+x^{\frac{3}{2}}}\\ (x+x^{3/2})f^2 &= x+1\\ x^{3/2}f^2 &= (x+1)-xf^2\\ x^3f^4&=[(x+1)-xf^2]^2\\ &=(x+1)^2-2x(x+1)f^2+x^2f^4\\ (x^3-x^2)f^4 + 2x(x+1)f^2-(x+1)^2&=0\\ p_4 =&\ x^3-x^2,\\ p_3 =&\ 0,\\ p_2 =&\ 2x(x+1),\\ p_1 =&\ 0,\\ p_0 =&\ -(x+1)^2\\

The functions defined on R\Bbb{R} that we have looked so far are all algebraic

We have \Setpolynomials\Setrational functions\Setalgebraic functions\Set{polynomials}\subseteq\Set{rational\ functions}\subseteq\Set{algebraic\ functions}

All other types of functions defined on R\Bbb{R} or parts of it are called transcendental functions

Examples of these types of functions are the trigonometric functions (sinx,cosx,tanx,secx,cscx,cotx)(\sin x,\cos x,\tan x,\sec x, \csc x, \cot x) and their inverses bdg-warningnot discussed in this course

Exponential Functions and their inverses ie logarithms and many more

The first function n!n! can be considered to be the values of the transcendental function Γ(x)\Gamma(x) Gamma Function when xx is an integer, and thus is essentially a transcendental function

In fact, Γ(n+1)=n!\Gamma(n+1) = n! bdg-dangerDon't need to know this

Γ(z)=0+tz1etdt\Gamma(z)=\int_0^{+\infty}t^{z-1}e^{-t}dt

Exponential Functions and Logarithms

Let bR,b>1b\in\Bbb{R}, b>1 For every rational number xx we can define bxb^x as we have seen before

The function y=bxy=b^x is called the exponential function with base bb

We can extent the definition of bxb^x to al real values of x by a process called definition by continuity

We note some facts about real and rational numbers

Every irrational number can be approximated to any accuracy by a rational number

The formal way to say this is:

Every irrational number is the limit of a sequence of rational numbers ordered

A sequence is a subset \Seta1,a2,,an,=ann=1\Set{a_1, a_2, \cdots,a_n,\cdots}={a_n}^\infty_{n=1} order matters
If aR\Q=Qc=a\in\Bbb{R}\backslash\Bbb{Q}=\Bbb{Q}^c= irrational numbers
then \Setann=1Q\exists\Set{{a_n}^\infty_{n=1}}\subseteq\Bbb{Q} such that x=limn+anx=\lim_{n\to +\infty}a_n

We then define bx=limn+(ban)b^x=\lim_{n\to +\infty}(b^{a_n})

In practical terms, to evaluate bxb^x, xx irrational take a rational number, r, very close to x and evaluate brb^r and say that effectively this is bxb^x. How close rr must be to xx depends on bb and the degree of accuracy required

Traditionally a commonly base was 10, ie y=10xy=10^x Today, due to influence of computer science, y=2xy=2^x is being used more and more

There is a special base, ee = Euler's number is in y=exy=e^x that arises from calculus

e=\sum_{k=0}^{+\infty}\frac{1}{k!}&=1+ \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \cdots\\ &=1+1+\frac{1}{2}+ \frac{1}{6} + \frac{1}{24} + \cdots\\ &= 2.718281882845904523535360287471352662497757\cdots

ee is a irrational number

In fact ee is a special type of irrational number called transcendental

From graph we see exponential functions are 1-1 hence they have a inverse

Properties of Exponential Functions

b^xb^y&=b^{x+y}\\ \frac{b^x}{b^y}&=b^{x-y}\\ (b^x)^y&=b^{xy}\\ b^{-x}&=\frac{1}{b^x}\\ b^0&=1\\

Logarithms

y=ba    logb(y)=ay = b^a \iff log_b(y) = a

bdg-secondaryProof 1

Let\ z &= log_b(xy), a=log_b(x), v+log_b(y)\\ Then\\ b^z&=xy\ and b^u &= x\\ b^v&=y\\ so\ b^z&=xy=b^ub^v=b^{u+v}

and since the exponential function is 1-1

this tells us that z=u+vz=u+v

ie,
logb(xy)=logbx+logbylog_b(xy) = log_bx +log_by

bdg-secondaryProof 2

Let\ u &= log_b(\frac{1}{x}), v=log_b(x)\\ Then\ b^u&=\frac{1}{x}\ , b^v = x b^\frac{1}{u} &= x\\ b^{-u}&=x\\ \therefore -u=v\ or\ u=-v\\ ie\ log_b(1/x)=-;pg_b(x)\\

We now use the previous proof repeatedly to get the result nZ\forall n\in\Bbb{Z} then nQ\forall n\in\Bbb{Q} and then by continuity for nR\forall n\in\Bbb{R}

logb(xn)=nlogbxlog_b(x^n) = n\log_bx

Change of Base

Let loga(x)=zlog_a(x)=z then x=azx=a^z so that logb(x)=logb(az)=zlogb(a)log_b(x)=log_b(a^z)=z\log_b(a) or

loga(x)=logb(x)logb(a)log_a(x)=\frac{log_b(x)}{log_b(a)}

Additional Proof

Suppose log23=pq,(p,q)>0log_23=\frac{p}{q},(p,q)>0
3=2pq3=2^{\frac{p}{q}} or 3q=2p3^q=2^p
This is impossible since 3q3^q is odd and 2p2^p is even

Now

2log23=(212)log23=212log23=2log23=3\sqrt{2}^{\log_23}=(2^{\frac{1}{2}})^{log_23}=2^{\frac{1}{2}\log_23}=2{log_2\sqrt{3}}=\sqrt{3}

which is irrational

Now 2log232log_23 is also irrational and (2)2log23=(22)2log23=2log23=3(\sqrt{2})^{2log_23}=(\sqrt{2}^2)^{2log_23}=2^{log_23}=3

Thus (irrational)irrational(irrational)^{irrational} can be irrational or rational

The number (2)2(\sqrt{2})^{\sqrt{2}} is the square root of Hilbert's number 222^{\sqrt{2}} and the head part is to show 222^{\sqrt{2}} is irrational

Floor and Ceiling Function

The functions are important in discrete mathematics because they take a continuous variable xx and turn it into a discrete integer variable

The functions rounds down to the nearest integer while the ceiling functions rounds up to the nearest integer

Floor Function

x\lfloor x\rfloor Largest Integer less than or equal to xx

This is called the greatest integer function or the integer part of x and is written [x][x]

Ceiling Function

x\lceil x\rceil Smallest Integer greater than or equal to xx

Because of how these look graphed, floor and ceiling functions are called step functions

Growth of Functions

Here we are concerned with the behavior of functions for very large values of the variable that is we consider

limx+f(x) or limxf(x)\lim_{x\to +\infty}f(x)\ or\ \lim_{x\to -\infty}f(x)

To do this we need our functions to be defined in a neighborhood of infinity

If we consider the limit at ++\infty, then the dom(f)dom(f) must contain an interval of the form [a,+)=\SetxRxa[a,+\infty)=\Set{x\in\Bbb{R}\mid x\ge a}

If we are considering the limit at -\infty, then dom(f)dom(f) must contain an interval of the form (,a]=\SetxRxa(-\infty,a]=\Set{x\in\Bbb{R}\mid x\le a}

Rates of growth

Big O notation

Here we are comparing the rate of growth at \infty of two functions.
We will state all our results for functions defined in a neighborhood of ++\infty, We can easily state similar results fir -\infty. We do this because in computer science one uses these result to analyze the complexity of algorithm

Let f(x)f(x) and g(x)g(x) be defined in a neighborhood of ++\infty. That is, for some

a\in\Bbb{R}, [a,+\infty)\subseteq\ &dom(f)\\ [a,+\infty)\subseteq\ &dom(g)\\ or\\ [a,+\infty)\subseteq\ &dom(f)\cap dom(g)

We say f(x) is Big O g(x) as x+f(x)\text{ is Big O }g(x)\ as\ x\to +\infty and write f(x)=O(g(x))f(x)=O(g(x)) if
 real number (k,C),ka,C>0\exists\ real \ number\ (k,C), k\ge a, C>0
such stat f(x)Cg(x),xk|f(x)|\le C|g(x)|,\forall x\ge k
We also say f is dominated by g

The numbers kk,CC are called witnesses to f(x)=O(g(x))f(x)=O(g(x))

bdg-secondaryExample Let f(x)=4x3+2x2, g(x)=x3f(x)=4x^3+2x^2,\ g(x)=x^3 then f(x)=O(g(x))f(x)=O(g(x)) or f(x)=O(x3)f(x)=O(x^3)


bdg-dangerProof

Since dom(f)=dom(g)=Rdom(f) = dom(g) = \Bbb{R}, each contains neighborhood of ++\infty

Now, when x1x\ge 1, 4x3+2x24x3+2x3=6x34x^3+2x^2\le 4x^3 +2x^3 =6x^3
since for x1, x2 x3x\ge 1,\ x^2\ \le x^3
Thus for x1x\ge 1,

f(x)=4x3+2x26g(x)=6x3+f(x)=O(x3)|f(x)|=4x^3+2x^2\le 6|g(x)| = 6x^3 + f(x)= O(x^3)

here the witnesses are (k,C)=(1,6)(k, C) = (1,6)

bdg-infoDefinition

A function f(x)f(x) defined on a neighborhood of infinity is called bounded at infinity if f(x)C,xkf(x)\le C, \forall x\ge k

We write f(x)=O(1) as x+f(x) = O(1)\ as\ x\to +\infty

Example:

sinx=O(1) as x+ \sin x=O(1)\ as\ x\to +\infty

Big O is useful in evaluating limits at infinity when g(x)0g(x)\to 0 as x+x\to +\infty since if f(x)=O(g)f(x)=O(g) we have f(x)Cg(x)0 as x+|f(x)|\le C|g(x)|\to 0\ as\ x\to +\infty so f(x)0f(x)\to 0 as x+x \to +\infty, as well

The triangle inequality for absolute values says

a+ba+b, a,bR|a+b|\le |a|+|b|,\ \forall a, b\in\Bbb{R}

This is easily generalized to any finite sum of numbers:

b1++bnb1++bn|b_1+\cdots +b_n|\le |b_1|+\cdots +|b_n|

Now for x1x\ge 1,

|f(x)| &= | a_k x^k + \cdots + a_0 |\\ &\le | a_k | | x^k| + \cdots + | a_1 | | x| + |a_0|\\ &= (|a_k| + \cdots + |a_0|) |x^k| =C|x^k|

Thus, f(x)=O(xk)f(x)=O(x^k) as x+x\to +\infty whenever ff a polynomial of degree kk

We return to the question of big O estimate

First consider what it means for f(x)f(x) to be not O(g(x))O(g(x))

To do this we formally negate the definition of f(x)=O(g(x))f(x)=O(g(x)) as x+x\to +\infty

¬(k,C>0   xkf(x)Cg(x))k,C>0,f(x0)>Cg(x) for some x0k \neg (\exists k, \exists C > 0\ \ \ x\ge k\to |f(x)|\le C|g(x))\\ \equiv\forall k, \forall C > 0, |f(x_0)|>C|g(x)|\ for\ some\ x_0\ge k

bdg-secondaryExample Let f(x)=x2 , g(x)=xf(x)=x^2\ ,\ g(x)=x

Let c>0c>0 be arbitrary, then
f(x)=x2>Cx|f(x)|= |x|^2>C|x| whenever x>C|x|>C, ie, x>Cx>C
take karbbdg-dangerwhat, x0=max(C+1,k)x_0 = max(C + 1, k)

Thus f(x0)>Cg(x0)|f(x_0)| > C | g(x_0) | for this x0x_0
So, x2x^2 is not O(x)O(x)

bdg-secondaryExample 1 let f(n)=n!f(n) = n!

then n!=123nnnn=nnn! = 1\cdot 2 \cdot 3 \cdots n \le n \cdot n \cdots n = n^n
thus n!=O(nn)n! = O(n^n) as n+n\to +\infty

bdg-secondaryExample 2 Let fb(n)=logbn,b>1f_b(n) = log_bn, b> 1

Now it is easily shown that n<2n,n1n<2^n, \forall n\ge 1

log2(n)<lof2(2n)=nlog_2(n) < lof_2(2^n) = n

and, using change of base formula for logarithms

logbn=log2nlog2b<1log2knlog_bn = \frac{log_2n}{log_2b}<\frac{1}{log_2k}\cdot n

so logb(n)=O(n)log_b(n) = O(n) as n+n\to +\infty for any base b>1b>1


bdg-primaryTheorem 3 Let f1(x)=O(g1(x)),f2(x)=O(g2(x))f_1(x)=O(g_1(x)), f_2(x)=O(g_2(x)) as x+x\to +\infty

Then\


a) f1(x)+f2(x)=O(max(g1(x),g2(x)))f_1(x) + f_2(x) = O(max(|g_1(x)|, |g_2(x)|)) as x+x\to +\infty


bdg-secondaryProof

|f_1(x) + f_2(x)| &\subseteq |f_1(x)| + |f_2(x)|\\ &\subseteq C_1|g_1(x)| + C_2|g_2(x)|\\ &\subseteq (C_1 + C_2)\ \max(|g_1(x)|,|g_2(x)|)\ \forall x\ \ge \max(k_1,k_2)

b) f1(x)f2(x)=O(g1(x)g2(x))f_1(x) \cdot f_2(x) = O(g_1(x)\cdot g_2(x)) as x+x\to +\infty


bdg-secondaryProof

|f_1(x)f_2(x)| &= |f_1(x)| \cdot |f_2(x)|\\ &\le C_1|g_1(x)| \cdot C_2|g_2(x)|\\ &\subseteq (C_1C_2)|g_1(x)\cdot g_2(x)|\\ \\ \forall x \ge \max (k_1, k_2)

bdg-successCorollary Let f1(x)=O(g(x))+f2(x)=O(g(x))f_1(x)=O(g_(x)) + f_2(x)=O(g(x)) as x+x\to +\infty

Then,
a) f1(x)+f2(x)=O(g(x))f_1(x) +f_2(x) = O(g(x)) as x+x\to +\infty
b) f1(x)f2(x)=O(g2(x))f_1(x)\cdot f_2(x) = O(g^2(x)) as x+x\to +\infty

bdg-secondaryExample Let f(n)=3nln(n!)+(n2+3)lnnf(n) = 3n \ln(n!) + (n^2 + 3)\ln n

We have ln(n!)ln(nn)=nlnn\ln (n!) \le \ln(n^n) = n\ln n so ln(n!)=O(nlnn)\ln (n!) = O(n\ln n)

and so 3nln(n!)=O(n2lnn)3n\ln (n!) = O(n^2\ln n) by theorem 3

also n2+3=O(n2)n^2 + 3 = O(n^2) by theorem 1 so
(n2+3)lnn=O(n2lnn)(n^2 + 3)\ln n = O(n^2\ln n)

f(n)=O(n2lnn)\therefore f(n) = O(n^2\ln n) as n+n\to +\infty

bdg-secondaryExercise find a O-estimate for f(x)=(x+1)ln(x2+1)+3x2f(x)=(x+1)\ln(x_2+1) + 3x^2
bdg-successHint 0<xlnxx20<x\ln x\le x^2 for x>1x>1

The O-estimate of a function gives an upper bound for the growth of f(x) as x+x\to +\infty (or as xx\to -\infty)

The Ω\Omega-estimate gives a lower bound for the growth of a function